package week_09;

/**
 * 36. 有效的数独
 * 请你判断一个 9x9 的数独是否有效。只需要 根据以下规则 ，验证已经填入的数字是否有效即可。
 * <p>
 * 数字 1-9 在每一行只能出现一次。
 * 数字 1-9 在每一列只能出现一次。
 * 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。（请参考示例图）
 * 数独部分空格内已填入了数字，空白格用 '.' 表示。
 * <p>
 * 注意：
 * <p>
 * 一个有效的数独（部分已被填充）不一定是可解的。
 * 只需要根据以上规则，验证已经填入的数字是否有效即可。
 * <p>
 * <p>
 * 示例 1：
 * <p>
 * <p>
 * 输入：board =
 * [['5','3','.','.','7','.','.','.','.']
 * ,['6','.','.','1','9','5','.','.','.']
 * ,['.','9','8','.','.','.','.','6','.']
 * ,['8','.','.','.','6','.','.','.','3']
 * ,['4','.','.','8','.','3','.','.','1']
 * ,['7','.','.','.','2','.','.','.','6']
 * ,['.','6','.','.','.','.','2','8','.']
 * ,['.','.','.','4','1','9','.','.','5']
 * ,['.','.','.','.','8','.','.','7','9']]
 * 输出：true
 * 示例 2：
 * <p>
 * 输入：board =
 * [['8','3','.','.','7','.','.','.','.']
 * ,['6','.','.','1','9','5','.','.','.']
 * ,['.','9','8','.','.','.','.','6','.']
 * ,['8','.','.','.','6','.','.','.','3']
 * ,['4','.','.','8','.','3','.','.','1']
 * ,['7','.','.','.','2','.','.','.','6']
 * ,['.','6','.','.','.','.','2','8','.']
 * ,['.','.','.','4','1','9','.','.','5']
 * ,['.','.','.','.','8','.','.','7','9']]
 * 输出：false
 * 解释：除了第一行的第一个数字从 5 改为 8 以外，空格内其他数字均与 示例1 相同。
 * 但由于位于左上角的 3x3 宫内有两个 8 存在, 因此这个数独是无效的。
 */
public class ValidSudoku_my_36 {
    int n;
    int m;
    int[] nums;

    public boolean isValidSudoku(char[][] board) {
        // 判断有没有效 是否可解 N * M 的二维数组
        // 每一个位置可以hash 一个 i*n+j
        // 对该数验证是否合法:
        // 同一行 同一列 同一个3*3 小方格是否重复
        n = board.length;
        m = board[0].length;
        nums = new int[n * m + 1];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (board[i][j] != '.') nums[num(i, j)] = board[i][j] - '0';
            }
        }

        // 对每个九宫格校验一次
        for (int i = 0; i < 9; i += 3) {
            for (int j = 0; j < 9; j += 3) {
                System.out.println("top:i:" + i + "j:" + j);
                if (!valid9Patch(i, j)) return false;
            }
        }
        return true;
    }

    public boolean valid9Patch(int row, int col) {
        int[] p9 = new int[9 + 1];

        for (int i = row; i < row + 3; i++) {
            for (int j = col; j < col + 3; j++) {
                System.out.println("in:i:" + i + "j:" + j);
                int k = nums[num(i, j)];
                if (k != 0 && p9[k] == 1) return false;
                if (k != 0 && !validCross(i, j, k)) return false;
                p9[k] = 1;
            }
        }
        return true;
    }

    private boolean validCross(int row, int col, int k) {
        for (int i = 0; i < 9; i++) {
            if (i != row && nums[num(i, col)] == k) return false;
        }
        for (int j = 0; j < 9; j++) {
            if (j != col && nums[num(row, j)] == k) return false;
        }
        return true;
    }

    public int num(int i, int j) {
        return i * n + j;
    }

    public static void main(String[] args) {
        char[][] arr = new char[][]{
                {'.', '.', '5', '.', '.', '.', '.', '.', '6'},
                {'.', '.', '.', '.', '1', '4', '.', '.', '.'},
                {'.', '.', '.', '.', '.', '.', '.', '.', '.'},
                {'.', '.', '.', '.', '.', '9', '2', '.', '.'},
                {'5', '.', '.', '.', '.', '2', '.', '.', '.'},
                {'.', '.', '.', '.', '.', '.', '.', '3', '.'},
                {'.', '.', '.', '5', '4', '.', '.', '.', '.'},
                {'3', '.', '.', '.', '.', '.', '4', '2', '.'},
                {'.', '.', '.', '2', '7', '.', '6', '.', '.'}

        };
        ValidSudoku_my_36 test = new ValidSudoku_my_36();
        System.out.println(test.isValidSudoku(arr));
    }
}
